package com.fengdi.solutions.esay;

import com.fengdi.publicObject.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class _257_Binary_tree_path {
    public List<String> binaryTreePaths(TreeNode root) {
        final List<String> result = new ArrayList<>();
        final List<Integer> path = new ArrayList<>();

        if(root == null) return result;
        if(root.left == null && root.right == null) {
            result.add(String.valueOf(root.val));
            return result;
        }

        dfs(root, path, result);
        return result;
    }

    public void dfs(TreeNode root, List<Integer> path, List<String> result) {
        if(root == null) return;

        if(root.left == null && root.right == null) {
            path.add(root.val);
            result.add(generateTreePath(path));
            return;
        }

        path.add(root.val);
        dfs(root.left, path, result);
        dfs(root.right, path, result);
        path.removeLast();
    }

    public String generateTreePath(List<Integer> path) {
        if(path.isEmpty()) return "";

        if(path.size() == 1) {
            return String.valueOf(path.getFirst());
        }

        StringBuilder result = new StringBuilder(path.getFirst().toString());
        for(int i = 1; i < path.size(); i++) {
            result.append("->").append(path.get(i));
        }

        return result.toString();
    }
}
